# Convex Hull

• 2026년 7월 15일 알고리즘
  추가 설명 — 평행한 변이 만드는 동률과 대척점 쌍 열거

  볼록 껍질 ⑤의 Rotating Calipers 뼈대는 평행한 변이 있어도 지름 값이 옳다. 이 글은 대척점 쌍 열거가 왜 별개 문제인지, 평행한 변이 만드는 동률과 교차 쌍을 어떻게 채우는지를 다룬다. 완전성(빠짐없음)은 얻되 유일성(중복 없음)은 얻지 못하며, 그 차이가 어디서 오는지까지 밝힌다.

• 2026년 7월 14일 알고리즘
  볼록 껍질 ⑤ — 가장 먼 두 점과 Rotating Calipers

  볼록 껍질을 도구로 써서 평면의 가장 먼 두 점(지름)을 찾는다. 가장 먼 쌍은 껍질 꼭짓점이며, 평행선을 돌리며 대척점 쌍만 훑는 Rotating Calipers로 모든 쌍 O(N²) 대신 O(N)에 얻는다.

• 2026년 7월 13일 알고리즘
  볼록 껍질 ④ — 분할 정복과 공통 접선

  점들을 절반으로 갈라 각각의 껍질을 재귀로 구한 뒤 공통 접선(common tangent)으로 잇는 분할 정복을 다룬다. 접선을 O(N)에 찾는 선형 워킹을 증명까지 따라가고, 이진 탐색을 겹쳐 O(log²N)으로 줄이는 아이디어와 그 아이디어가 아직 채우지 못한 부분을 밝힌다.

• 2026년 7월 10일 알고리즘
  추가 설명 — 균형 트리에서 접선을 O(log N)에 찾기

  볼록 껍질 ③이 미뤄둔 부분. x좌표로 정렬된 볼록 사슬을 균형 트리에 담아, 외부 점에서 그은 접선의 접점을 O(log N)에 찾는 법. 후보 꼭짓점의 두 이웃 변에 CCW를 돌려 방향을 판정하고, 그것이 왜 이진 탐색이 되는지 따라간다.

• 2026년 7월 9일 알고리즘
  볼록 껍질 ③ — Plane Sweeping과 동적 갱신

  점을 하나씩 더해 가며 볼록 껍질을 유지하는 두 문제를 다룬다. 점을 x좌표 순으로 추가하는 Plane Sweeping(O(N²)에서 균형 트리로 O(N log N))과, 완성된 껍질에 점이 계속 추가되는 동적 볼록 껍질이다.

• 2026년 7월 8일 알고리즘
  볼록 껍질 ② — Graham Scan과 정렬 하한

  Package Wrapping은 걸음마다 점 전체를 훑어 최악 O(N²)이다. Graham Scan은 각도 정렬 한 번 뒤 스택으로 좌회전만 남겨 O(N log N)에 볼록 껍질을 구한다. 정렬을 볼록 껍질로 환원해 Ω(N log N) 하한까지 확인한다.

• 2026년 7월 7일 알고리즘
  볼록 껍질 ① — 정의, CCW, 그리고 Package Wrapping

  평면의 점들을 모두 감싸는 가장 작은 볼록 다각형, 볼록 껍질(convex hull)을 구한다. O(N³) 브루트포스에서 출발해 세 점의 회전 방향을 정수 연산으로 판정하는 CCW를 유도하고, 포장지로 감싸듯 껍질을 찾는 Package Wrapping(O(NH))까지 다룬다.